package com.zhaopin.theswordreferstooffer;

/**
 * @author yin.peide
 * @date 2021-06-02 10:42
 * 面试题6： 重建二叉树
 */
public class Offer6 {

    public static void main(String[] args) {
        SolutionTree solutionTree = new SolutionTree();
        //前序遍历的数组
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        //中序遍历的数组
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode treeNode = solutionTree.buildTree(pre, in);
        //二叉树 前序遍历结果： {1,2,4,7,3,5,6,8}
        //二叉树 中序遍历结果： {4,7,2,1,5,3,8,6}
        System.out.println(treeNode);

    }
}

class TreeNode {

    private int value;
    private TreeNode left;
    private TreeNode right;

    public void init (TreeNode left,TreeNode right){
        setLeft(left);
        setRight(right);
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    TreeNode(int x) {
        value = x;
    }
}


class SolutionTree {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0, 0, inorder.length - 1, preorder, inorder);
    }

    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        //创建结点--> 先序遍历的第一个就是首节点
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = 0;
        //找到当前节点root在中序遍历中的位置，然后再把数组分两半
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.getValue()) {
                index = i;
                break;
            }
        }
        root.setLeft(helper(preStart + 1, inStart, index - 1, preorder, inorder));
        root.setRight(helper(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder));
        return root;
    }
}

